Search results for "Clustering effect"

showing 3 items of 3 documents

Balanced Words Having Simple Burrows-Wheeler Transform

2009

The investigation of the "clustering effect" of the Burrows-Wheeler transform (BWT) leads to study the words having simple BWT , i.e. words w over an ordered alphabet $A=\{a_1,a_2,\ldots,a_k\}$, with $a_1 < a_2 < \ldots <a_k$, such that $bwt(w)$ is of the form $a_k^{n_k} a_{k-1}^{n_{k-1}} \cdots a_1^{n_1}$, for some non-negative integers $n_1, n_2, \ldots, n_k$. We remark that, in the case of binary alphabets, there is an equivalence between words having simple BWT, the family of (circular) balanced words and the conjugates of standard words. In the case of alphabets of size greater than two, there is no more equivalence between these notions. As a main result of this paper we prove that, u…

CombinatoricsConjugacy classClustering effectBurrows–Wheeler transformSettore INF/01 - InformaticaBurrows Wheeler Transform Combinatorics on Words Balanced sequences epistandard rich words words having simple BWTBinary numberBurrows-Wheeler TransformAlphabetBinary alphabetBurrows-Wheeler Transform; Clustering effectMathematics
researchProduct

Burrows-Wheeler transform and Run-Length Enconding

2017

In this paper we study the clustering effect of the Burrows-Wheeler Transform (BWT) from a combinatorial viewpoint. In particular, given a word w we define the BWT-clustering ratio of w as the ratio between the number of clusters produced by BWT and the number of the clusters of w. The number of clusters of a word is measured by its Run-Length Encoding. We show that the BWT-clustering ratio ranges in ]0, 2]. Moreover, given a rational number \(r\,\in \,]0,2]\), it is possible to find infinitely many words having BWT-clustering ratio equal to r. Finally, we show how the words can be classified according to their BWT-clustering ratio. The behavior of such a parameter is studied for very well-…

Discrete mathematicsRational numberBurrows–Wheeler transformComputer scienceComputer Science (all)0102 computer and information sciences02 engineering and technologyBurrows-Wheeler transform01 natural sciencesBurrows-Wheeler transform; Clustering effect; Run-length encoding; Theoretical Computer Science; Computer Science (all)Theoretical Computer ScienceClustering effect010201 computation theory & mathematicsRun-length encoding0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processingCluster analysisWord (computer architecture)Run-length encoding
researchProduct

The Burrows-Wheeler Transform between Data Compression and Combinatorics on Words

2013

The Burrows-Wheeler Transform (BWT) is a tool of fundamental importance in Data Compression and, recently, has found many applications well beyond its original purpose. The main goal of this paper is to highlight the mathematical and combinatorial properties on which the outstanding versatility of the $BWT$ is based, i.e. its reversibility and the clustering effect on the output. Such properties have aroused curiosity and fervent interest in the scientific world both for theoretical aspects and for practical effects. In particular, in this paper we are interested both to survey the theoretical research issues which, by taking their cue from Data Compression, have been developed in the conte…

Theoretical computer scienceSettore INF/01 - InformaticaBurrows–Wheeler transformmedia_common.quotation_subjectTheoretical researchContext (language use)Data_CODINGANDINFORMATIONTHEORYBurrows Wheeler transform; Clustering effect; Combinatorial propertiesCombinatorial propertiesBurrows Wheeler transformCombinatorics on wordsClustering effectBWT balancing optimal partitioning text-compressionCuriosityArithmeticCluster analysisFocus (optics)media_commonData compressionMathematics
researchProduct